`
https://leetcode.cn/problems/minimum-path-sum/
`

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const m = grid.length, n = grid[0].length
  const dp = new Array(m).fill().map(() => new Array(n).fill(0));

  // 起点的最小路径和就是它本身
  dp[0][0] = grid[0][0]

  // 第一行的最小路径和只能从左边过来
  for (let i = 1; i < n; i++) {
    dp[0][i] = dp[0][i - 1] + grid[0][i]
  }

  // 第一列的最小路径和只能从上面下来
  for (let i = 1; i < m; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0]
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      // 上面的最小路径和和左边的最小路径和，取较小值加上当前值
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
    }
  }

  return dp[m - 1][n - 1]
};